5.5 Use the Principle of Mathematical Induction (Appendix 1) to prove that the move method in the Towers of Hanoi example is correct, that is, for any integern > = 1, move (n, orig, dest, temp) returns the steps to move n disks from pole orig to pole dest. Hint: for n = 1, 2, 3, . . . , let Sn be the statement: move (n, orig, dest, temp) returns the steps to move n disks from any pole orig to any other pole dest. a. base case. Show that S1 is true. b. inductive case. Let n be any integer greater than 1 and assume Sn−1 is true. Then show that Sn is true. According the code of the move method, what happens when move (n, orig, dest, temp) is called and n is greater than 1? | |
| View Solution | |
| << Back | Next >> |